#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int>& a,int left,int mid,int right)
{
	vector<int> t1,t2;
	for(int i=left;i<=mid;i++)
		t1.push_back(a[i]);
	for(int i=mid+1;i<=right;i++)
		t2.push_back(a[i]);
	int lpos=0,rpos=0,k=left;
	while(lpos<t1.size() && rpos<t2.size())
	{
		if(t1[lpos]<t2[rpos])
		{
			a[k]=t1[lpos];
			lpos++;
		}
		else{
			a[k]=t2[rpos];
			rpos++;
		}
		k++;
	}
	while(lpos<t1.size())
	{
		a[k]=t1[lpos];
		k++;
		lpos++;
	}
	while(rpos<t2.size())
	{
		a[k]=t2[rpos];
		k++;
		rpos++;
	}
}
void mergeSort(vector<int>& a,int left,int right)
{
	if(left>=right)
		return;
	int mid=left+(right-left)/2;
	mergeSort(a,left,mid);
	mergeSort(a,mid+1,right);
	merge(a,left,mid,right);
}

int main()
{
	
	vector<int> a({10,9,8,7,6,2,3,1,4,5});
	mergeSort(a,0,a.size()-1);
	for(int i=0;i<a.size();i++)
	{
		cout<<a[i]<<' ';
	}
	
	return 0;
}
